// 版权归Go作者所有。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

package ssa

import (
	"cmd/internal/src"
)

// fuseEarly运行fuse（f，Fusetypelain | fuseTypeIntInRange）。
func fuseEarly(f *Func) { fuse(f, fuseTypePlain|fuseTypeIntInRange) }

// 机身运行保险丝（f，Fusetyplain | fuseTypeIf | fuseTypeBranchRedirect）。
func fuseLate(f *Func) { fuse(f, fuseTypePlain|fuseTypeIf|fuseTypeBranchRedirect) }

type fuseType uint8

const (
	fuseTypePlain fuseType = 1 << iota
	fuseTypeIf
	fuseTypeIntInRange
	fuseTypeBranchRedirect
	fuseTypeShortCircuit
)

// fuse通过连接基本块简化了控制流程。
func fuse(f *Func, typ fuseType) {
	for changed := true; changed; {
		changed = false
		// 自始至终进行熔合，以避免fuseBlockPlain中的二次行为。见第13554期。
		for i := len(f.Blocks) - 1; i >= 0; i-- {
			b := f.Blocks[i]
			if typ&fuseTypeIf != 0 {
				changed = fuseBlockIf(b) || changed
			}
			if typ&fuseTypeIntInRange != 0 {
				changed = fuseIntegerComparisons(b) || changed
			}
			if typ&fuseTypePlain != 0 {
				changed = fuseBlockPlain(b) || changed
			}
			if typ&fuseTypeShortCircuit != 0 {
				changed = shortcircuitBlock(b) || changed
			}
		}
		if typ&fuseTypeBranchRedirect != 0 {
			changed = fuseBranchRedirect(f) || changed
		}
		if changed {
			f.invalidateCFG()
		}
	}
}

// fuseBlockIf处理以下情况，其中s0和s1为空块。
// None
// b b b b
// \ / \ /    | \  /    \ / |     | |
// s0 s1 | s1 s0 | ||
// \ /      | /         \ |     | |
// 党卫军
// None
// 如果ss中的所有Phi ops在对应于
// s0、s1和b，然后分支可以断开。
// 这种优化通常出现在具有多个参数的switch语句中
// case子句中的表达式：
// 开关n{
// 案例1、2、3：返回4
// }
// TODO:如果ss不包含任何OpPhis，那么s0和s1都是死代码。
func fuseBlockIf(b *Block) bool {
	if b.Kind != BlockIf {
		return false
	}
	// s0或s1有多少PreD并不重要。
	var ss0, ss1 *Block
	s0 := b.Succs[0].b
	i0 := b.Succs[0].i
	if s0.Kind != BlockPlain || !isEmpty(s0) {
		s0, ss0 = b, s0
	} else {
		ss0 = s0.Succs[0].b
		i0 = s0.Succs[0].i
	}
	s1 := b.Succs[1].b
	i1 := b.Succs[1].i
	if s1.Kind != BlockPlain || !isEmpty(s1) {
		s1, ss1 = b, s1
	} else {
		ss1 = s1.Succs[0].b
		i1 = s1.Succs[0].i
	}
	if ss0 != ss1 {
		if s0.Kind == BlockPlain && isEmpty(s0) && s1.Kind == BlockPlain && isEmpty(s1) {
			// 两种特殊情况，其中s0、s1和ss均为空块。
			if s0 == ss1 {
				s0, ss0 = b, ss1
			} else if ss0 == s1 {
				s1, ss1 = b, ss0
			} else {
				return false
			}
		} else {
			return false
		}
	}
	ss := ss0

	// None
	// （图中第二、第三和第四种情况）。

	for _, v := range ss.Values {
		if v.Op == OpPhi && v.Uses > 0 && v.Args[i0] != v.Args[i1] {
			return false
		}
	}

	// 我们不需要将s0和s1的PRED重定向到ss，
	// 下面的优化将实现这一点。
	b.removeEdge(0)
	if s0 != b && len(s0.Preds) == 0 {
		s0.removeEdge(0)
		// 将s0中的任何（死）值移动到b，
		// 它们将在下一个死码过程中被消除。
		for _, v := range s0.Values {
			v.Block = b
		}
		b.Values = append(b.Values, s0.Values...)
		// 清除s0。
		s0.Kind = BlockInvalid
		s0.Values = nil
		s0.Succs = nil
		s0.Preds = nil
	}

	b.Kind = BlockPlain
	b.Likely = BranchUnknown
	b.ResetControls()
	// b中的值可能是死代码，及时清除它们可能会导致错误
	// 获得新的优化机会。
	// 首先将可以删除的死值放入一个值切片中。
	// 然后在重置死值之前，将它们的参数放入walkValues中
	// 在walkValues中，因为参数也可能成为死值。
	walkValues := []*Value{}
	for _, v := range b.Values {
		if v.Uses == 0 && v.removeable() {
			walkValues = append(walkValues, v)
		}
	}
	for len(walkValues) != 0 {
		v := walkValues[len(walkValues)-1]
		walkValues = walkValues[:len(walkValues)-1]
		if v.Uses == 0 && v.removeable() {
			walkValues = append(walkValues, v.Args...)
			v.reset(OpInvalid)
		}
	}
	return true
}

// isEmpty报告b是否包含任何活动值。
// 可能有误报。
func isEmpty(b *Block) bool {
	for _, v := range b.Values {
		if v.Uses > 0 || v.Op.IsCall() || v.Op.HasSideEffects() || v.Type.IsVoid() {
			return false
		}
	}
	return true
}

func fuseBlockPlain(b *Block) bool {
	if b.Kind != BlockPlain {
		return false
	}

	c := b.Succs[0].b
	if len(c.Preds) != 1 {
		return false
	}

	// 如果一个块恰好以语句标记结束，
	// 尽量保存它。
	if b.Pos.IsStmt() == src.PosIsStmt {
		l := b.Pos.Line()
		for _, v := range c.Values {
			if v.Pos.IsStmt() == src.PosNotStmt {
				continue
			}
			if l == v.Pos.Line() {
				v.Pos = v.Pos.WithIsStmt()
				l = 0
				break
			}
		}
		if l != 0 && c.Pos.Line() == l {
			c.Pos = c.Pos.WithIsStmt()
		}
	}

	// 将b的所有值移到c。
	for _, v := range b.Values {
		v.Block = c
	}
	// 使用较大的价值片，以避免增长。
	// 但是，请注意避免c.值指向b.存储。
	// 见golang.org/issue/18602。
	// 保持元素的顺序是很重要的；维护
	// 调试信息取决于*值在块中的顺序。
	// 这也会导致订单发生变化（可能会影响其他订单）
	// 32位与64位编译的优化（可能还有编译器输出）
	// 平台（字大小影响分配桶大小影响切片容量）。
	if cap(c.Values) >= cap(b.Values) || len(b.Values) <= len(b.valstorage) {
		bl := len(b.Values)
		cl := len(c.Values)
		var t []*Value // 构造t=b.值，然后是c.值，但要注意分配。
		if cap(c.Values) < bl+cl {
			// 重新分配
			t = make([]*Value, bl+cl)
		} else {
			// 在正确的位置
			t = c.Values[0 : bl+cl]
		}
		copy(t[bl:], c.Values) // 可能在适当的地方
		c.Values = t
		copy(c.Values, b.Values)
	} else {
		c.Values = append(b.Values, c.Values...)
	}

	// 将b->c边替换为preds（b）->c
	c.predstorage[0] = Edge{}
	if len(b.Preds) > len(b.predstorage) {
		c.Preds = b.Preds
	} else {
		c.Preds = append(c.predstorage[:0], b.Preds...)
	}
	for i, e := range c.Preds {
		p := e.b
		p.Succs[e.i] = Edge{c, i}
	}
	f := b.Func
	if f.Entry == b {
		f.Entry = c
	}

	// 垃圾b，以防万一
	b.Kind = BlockInvalid
	b.Values = nil
	b.Preds = nil
	b.Succs = nil
	return true
}
